A machine can be configured to generate, compress, decompress, store, communicate, or otherwise process computer graphics that represent two-dimensional (2D) or three-dimensional (3D) objects. “UV mapping” is the process of generating a 2D UV map and a 2D texture map from a colored surface in 3D. A texture map is a 2D array of colored pixels used for texture mapping, which is the process of generating a colored surface in 3D from a UV map and a texture map. In this sense, UV mapping and texture mapping can be considers as inverses.
In computer graphics, a UV map refers to an assignment of each 3D point on a surface to a 2D point in a rectangular domain; that is, a UV map is a mathematical map from the coordinates of a 3D surface to the coordinates of a 2D image. For example, if the surface is represented by (e.g., expressed as) a list of surface elements (e.g., vertices, voxels, etc.), and the image is represented by a 2D array of pixels, then a UV map may be represented by a list of indices, the same length as the number of surface elements, indicating the index of the pixel in the image that corresponds to the surface element. UV mapping is the process of generating (e.g., from the list of surface elements) a list of correspondences along with an image (i.e., the texture map) such that the color of a surface element is equal to the color of its corresponding pixel in the texture map.
Mathematically, such an assignment can be represented by a function ƒ:→ mapping 3D points on a surface ⊂3 to 2D points in a rectangular domain ϵ2. That is, the 2D point (u, v)ϵ is assigned to the 3D point (x, y, z)ϵ if (u, v)=ƒ(x, y, z). Let I(u, v) denote the color of an image at the point (u, v)ϵ, and let S(x, y, z) denote the color of the surface at the point (x, y, z)ϵ. Here, to be concise, only color is discussed, but more general attributes besides color, such as transparency, normals, and the like, can be specified.
First, consider the technical problem of determining the color of the surface C(r, g, b) at each point (x, y, z) in a surface , given an image {I(u, v):(u, v)ϵ} and a UV map {ƒ(x, y, z):(x, y, z)ϵ}. This technical problem can be considered as a “forward” technical problem, for reasons that will become clear shortly. The technical solutions to this technical problem can be expressed in the following form:C(x,y,z)=I(ƒ(x,y,z)).
In computer graphics, the process of using this formula to render the color of a surface  is called texture mapping, and the image {I(u, v):(u, v)ϵ} is called a texture map. The surface  is usually represented by a mesh =(, ), where ={(xn, yn, zn)} is a list of vertices and ={(im, jm, km)} is a list of faces. Each vertex (xn, yn, zn)ϵ is a point in 3D and each face (im, jm, km)ϵ is a triple of indices into the list  of vertices. For conciseness and clarity, the discussion herein focuses on triangular meshes, but the systems and methods discussed herein are also applicable to more general polygonal meshes, such as quad meshes. The texture map {I(u, v):(u, v)ϵ} is usually represented by a 2D array of pixels, and the UV map {ƒ(x, y, z):(x, y, z)ϵ} is usually represented by coordinates (un, vn) in one-to-one correspondence with the vertices (xn, yn, zn) of the mesh. With these representations, if (x, y, z)ϵ is a 3D point on a face of the mesh, then it corresponds to a 2D point ƒ(x, y, z)=(u, v)ϵ as follows.
Suppose the face containing (x, y, z) has vertices (xn1, yn1, zn1), (xn2, yn2, zn2), and (xn3, yn3, zn3), and suppose that α1, α2, α3 are barycentric coordinates of (x, y, z), namely coefficients 0≤α1, α2, α3≤1 such that(x,y,z)=α1(xn1,yn1,zn1)+α2(xn2,yn2,zn2)+α3(xn3,yn3,zn3).Then,ƒ(x,y,z)=(u,v)=α1(un1,vn1)+α2(un2,vn2)+α3(un3,vn3).Thus, when a face on the surface is rasterized and rendered, each point (x, y, z) on the face obtains its color by looking up the color in the image at the corresponding location (u, v). Note that the point (u, v) may not lie exactly at the center of a pixel, so interpolation of some kind may be used to look up the color.
For dynamic (e.g., time-varying) surfaces, typically the mesh vertices (xn(t), yn(t), zn(t)) become functions of time and hence follow trajectories through space and time. Such a mesh can be called a dynamic or animated mesh. Typically, however, in a dynamic mesh, the UV coordinates (un, vn) remain constant. Thus a single texture map can be used for a dynamic mesh.
FIG. 1 is a conceptual diagram illustrating an example of UV mapping applied to a 3D object; that is, a process for determining a texture map {I(u, v):(u, v)ϵ} and a UV map {ƒ(x, y, z):(x, y, z)ϵ}, given the color of the surface C(x, y, z) at each point (x, y, z) in a surface , such that C(x, y, z)=I(ƒ(x, y, z)) holds. This can be considered an “inverse” technical problem relative to the “forward” technical problem discussed above. The process for determining such a texture map and a UV map from a surface can thus be called UV mapping, which is illustrated in FIG. 1.
In UV mapping, for each 3D point (x, y, z) on the surface , a corresponding 2D point t (u, v) on the texture map is determined, and the color C(x, y, z) (e.g., yellow, red, light blue, or dark green, as shown in FIG. 1) is copied from the surface to the texture map as I(u, v). Since the surface is usually represented by a mesh, the correspondence is usually determined by first determining, for each 3D vertex (xn, yn, zn) of each face of the mesh, a corresponding 2D point (un, vn) on the texture map. Then, the 2D point (u, v) corresponding to a point (x, y, z) on a face is obtained by calculating the barycentric coordinates of (x, y, z) with respect to the vertices of the face. This correspondence constitutes a UV map.
Once the texture map and the UV map are determined (e.g., by solving the “inverse” problem), they can be used for texture mapping (e.g., to solve the “forward” problem, such as when texturing the surface of a 3D model of the original 3D object). The solution to the (“inverse”) UV mapping problem is often not well-defined. That is, given the colors S on the surface , there can be many choices of I and ƒ such that C(x, y, z)=I(ƒ(x, y, z)).
FIG. 2 is a conceptual diagram illustrating examples of charting, which is one approach to solving the UV mapping problem by defining ƒ piecewise. That is, the domain of ƒ, namely , is partitioned into non-overlapping pieces 1, 2, 3, . . . such that ∪kk=, and ƒ is defined separately on each piece. The process of determining how to partition  into pieces 1, 2, 3, . . . is called charting, which is illustrated in FIG. 2. In FIG. 2, boundaries between such non-overlapping pieces are shown in red.
FIG. 3 is a conceptual diagram illustrating an example of UV mapping applied to a specific charting. Once the pieces of  are determined, the UV map ƒ is determined on each piece 1, 2, 3, . . . . This process is called chart parametrization, and involves flattening each piece k onto an image plane in such a way that the flattened pieces ƒ(k) do not overlap and such that there is little (e.g., minimal) local geometric distortion between the piece k and its flattened version ƒ(k), which is illustrated in FIG. 3, using the same example colors described above with respect to FIG. 1 and FIG. 2.
The flattened pieces ƒ(k) are called charts, and the collection of charts is called an atlas, by analogy with a seafarer's maps of the Earth, in which different pieces of the Earth appear on each chart. Because the surface is often represented by a mesh, charting can involve partitioning the mesh into sub-meshes. Then, chart parametrization may include assigning a 2D point (un, vn) to each 3D vertex (xn, yn, zn) of each face of each sub-mesh. Then, the atlas becomes a texture map, which can be used to re-color the surface. Charting and chart parametrization are often done jointly, and such a joint process is sometimes called atlas parametrization. Atlas parametrization is thus a form of UV mapping. As used herein, “atlas” refers both to a texture map of charts, and also to a texture map of charts in combination with the UV map that underlies it; that is, atlas refers to a representation of the result or output or solution of atlas parametrization or the UV mapping problem.
Atlas parametrization may have a goal of minimizing the distortion resultant from the stretching of the texture. Stretching may be impossible to avoid when flattening a 3D mesh onto a 2D plane, but it can be minimized. Texture mapping quality and performance may therefore benefit from an atlas parametrization algorithm able to minimize such distortion. For example, a texture stretch metric can be used to calculate how much the distortion affects a certain 2D mapping. FIG. 4 is a conceptual diagram illustrating an example of how the texture of a 3D surface (a) can be stretched by an unrefined atlas parametrization (b) and how the minimization of the texture stretch metric improves the final result (c).
For dynamic surfaces, temporal coherence can also be important. Changes in the geometry and topology due to motion can cause overlapping and sharp changes of the 2D polygons. Moreover, if the dynamic mesh does not track the surface with sub-pixel accuracy, the colors of the surface can drift in the texture map, causing temporal incoherence of the texture map. Temporally consistent meshing is a way to maximize temporal coherence in the texture map.
Compression of texture maps as images is common in computer graphics. If the texture maps are time-varying, as they may be for dynamic surfaces, then compressing the texture maps as video can be done. Compression techniques for images and video can be efficient performed using algorithms such as Advanced Video Codec (AVC)/H.264 or High Efficiency Video Coding (HEVC)/H.265. Maximizing the temporal coherence of the texture maps is a good way to exploit the compression efficiency of the video coding methods, which generally have very high performance when they are able to remove the temporal redundancy of a video sequence.
Improvements to the quality of texture map compression may be obtained by applying tracking techniques. For example, a tracking method may start by choosing a key-frame, meshing it, and calculating the UV map for it. Then, the mesh of the key-frame is fit to the neighboring frames by projecting the texture components, which in the meanwhile have moved in the 3D space, over the same 2D area as the tracked colors of the key-frame. As a result of this strategy, when the atlas is compressed by a traditional 2D based video encoder, the reduced motion of the scene can be well exploited, providing better results for the same bit-rates.
FIG. 5 is a conceptual diagram illustrating an example comparison of a decompressed untracked atlas to a decompressed tracked atlas. The top row shows a decoded sequence representing an untracked atlas. The bottom row shows a decoded sequence representing a tracked atlas, as well as the quality improvement attained when the atlas is tracked.
Unfortunately, atlas parametrization is a computationally heavy process whose complexity increases with the Level of Detail (LOD) of the mesh representation of the 3D object. In addition, when the meshes are parametrized on a plane, the textures are affected by stretching distortions.